package leetcode_500;

import java.util.HashMap;
import java.util.HashSet;


/**
 * AllOoneDataStructure_432_ 实现一个特殊Map 要求能保存key出现的次数  并能完成输出最小次数和最大次数的key 所有操作都在O(1)时间内完成
 * 2018年8月16日 下午3:14:29
 * @author 周杨
 * describe :用层构造 每层有两个指针 这两个指针指向比他大一层和小一层 每次对层操作 并用全局指针指向最高层和最底层 AC 55%
 *
 */
public class AllOoneDataStructure_432_ {
	
	Bucket head;
	Bucket tail;
	HashMap<String, Integer> keyCountMap;
	HashMap<Integer, Bucket> countBucketMap;
	
	public class Bucket {
        int count;
        Bucket prev;
        Bucket next;
        HashSet<String> keySet;
        public Bucket(int num) {
            this.count = num;
            this.keySet = new HashSet<String>();
        }
    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	/** Initialize your data structure here. */
	AllOoneDataStructure_432_() {
		this.head = new Bucket(Integer.MIN_VALUE);//初始化两个指针 并且让他们形成环 由此辨别是否层是否为空
        this.tail = new Bucket(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;
        this.keyCountMap = new HashMap<String, Integer>();
        this.countBucketMap = new HashMap<Integer, Bucket>();
    }
    
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (keyCountMap.containsKey(key)) {//如果有这一层 改变这一层
            change(key, 1);
        }
        else {
            keyCountMap.put(key, 1);
            if (head.next.count != 1) {  //没有层数为1的层
                addBucketAfter(new Bucket(1), head);
                countBucketMap.put(1, head.next);
            }
            head.next.keySet.add(key);//头的指针下一个指向1的层
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (keyCountMap.containsKey(key)) {
            int count = keyCountMap.get(key);
            if (count == 1) {
                keyCountMap.remove(key);
                removeKeyFromBucket(countBucketMap.get(count), key);
            }
            else change(key, -1);
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return tail.prev==head? "" : (String)tail.prev.keySet.iterator().next();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return head.next==tail? "" : (String)head.next.keySet.iterator().next();
    }
    
    /**
     * 2018年8月15日 下午5:19:19
     * @author 周杨
     * describe :改变这个key所指向的层 这个key是已经存在的
     * @param key
     * @param offset 这一层的增减值
     */
    public void change(String key, int offset) {
        //get count, update keyCountMap
        int count = keyCountMap.get(key);
        keyCountMap.put(key, count+offset);
        
        //get current bucket
        Bucket curBucket = countBucketMap.get(count);
  
        //new bucket
        Bucket newBucket;
        if (countBucketMap.containsKey(count+offset)) {//新层是否存在
            newBucket = countBucketMap.get(count+offset);
        }
        else {//没有新层 则new新层 并插入
            newBucket = new Bucket(count+offset);
            countBucketMap.put(count+offset, newBucket);
            addBucketAfter(newBucket, (offset==1? curBucket : curBucket.prev));//判断是否是增加1 如果是 则把原来的层连接到此层前
        }
        newBucket.keySet.add(key);
        removeKeyFromBucket(curBucket, key);//从原来层里移除
    }
    
    public void removeKeyFromBucket(Bucket cur, String key) {
        cur.keySet.remove(key);
        if (cur.keySet.size() == 0) {
            removeBucketFromList(cur);
            countBucketMap.remove(cur.count);
        }
    }
    
    public void removeBucketFromList(Bucket cur) {
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        cur.next = null;
        cur.prev = null;
    }
    
   
    
    /**
     * 2018年8月15日 下午5:16:39
     * @author 周杨
     * describe :把两个层连接起来
     * @param bucket
     * @param preBucket 
     */
    public void addBucketAfter(Bucket bucket, Bucket preBucket) {
        bucket.prev = preBucket;
        bucket.next = preBucket.next;
        preBucket.next.prev = bucket;
        preBucket.next = bucket;
    }

}
